In the related art, in data storage devices, such as a hard disk drive (HDD) or a solid state drive (SSD), use states of storage media are managed using a variety of management information, such as a conversion table where a logical address (LBA: Logical Block Address) and a physical address (PBA: Physical Block Address) are associated with each other. The logical address is a logical address of a storage medium that can be recognized by a host device, such as a server computer, a controller of a storage system or a personal computer. The physical address is an address that indicates a physical storage position of the storage medium.
As an example of the storage medium of the data storage device, a semiconductor storage element, such as a NAND-type flash memory, is known. This storage medium disables a random read/write operation of data, and needs to read/write data in a unit called a page, constructs a storage area of a unit called a block where plural pages are collected. In order to write new data in data written pages or blocks, written data needs to be erased in a block unit. That is, data can be sequentially written in a page unit with respect to pages of data erased blocks where data is not yet written, and overwrite of data is disabled with respect to data written pages.
A unit of read/write when the host device performs a data read/write operation with respect to the data storage device is called a sector and is determined independently from a page unit or a block unit. For example, a block size is determined as 512 kilobytes, a page size is determined as 4 kilobytes, and a sector size is determined as 512 bytes.
In the data storage device using the storage medium having the above-mentioned constraints, a block managing method that uses a size of the integral multiple of a block size as a management size of data in management information is adopted. When random write is requested from the host device in the block managing method, the data storage device reads data, which is not updated by the write request and is included in data stored in one or more blocks corresponding to a logical address area that is a range of logical addresses where write is requested by the host device, in a temporary storage area. The data storage device merges the data with write object data. The data storage device executes a process of erasing one or more new write object blocks, writes the merged data, and updates the management information such that the logical address area and one or more new write object blocks correspond to each other.
As described above, in the block managing method, since a data written size and a data read size in the data storage device is significantly larger than a data write requested size requested from the host device, a process time may increase and random write performance may be significantly deteriorated.
For this reason, in the data storage device using the storage medium having the above-mentioned constraints, the random write performance is improved using a log-structured method (for example, refer to Mendel Rosenblum and John K. Ousterhout, “The LFS Storage Manager”, Proceedings of the 1990 Summer Usenix, Anaheim, Calif., June 1990, pp. 315-324), which is executed by an operating system (OS) memory management or a file system.
In the data storage device using the log-structured method, write object data is sequentially written in ascending order of pages, regardless of a logical address designated by the write request from the host device. If a write request that designates a previously designated logical address again is made from the host device, the data storage device writes new write object data in a non-written page of a block where an erasing process is completed. The data storage device invalidates the page (page where data is written when the corresponding logical address is designated in the past) corresponding to the logical address in the management information, validates a page where new write object data is written, and associates the page with the corresponding logical address.
In the data storage device using the log-structured method, if the number of invalidated pages increases, the number of new blocks where data can be written and an erasing process is completed (i.e., the number of free blocks where data is not written after the erasing process) decreases and new data write may not be performed. For this reason, compaction (corresponding to garbage collection) is performed at appropriate timing.
In performing the compaction, the data storage device collects valid data stored in physical addresses that are not invalidated among the blocks including the invalidated pages, copies the valid data into a free block to move the valid data, and executes an erasing process on the blocks, from which the copy has been made, to generate a new free block. The data storage device can generate a free block from a write disabled block by performing the compaction. Even in a block where valid data is written by the move, if a non-written page exists, new write with respect to the page is enabled.
According to this log-structured method, since a data written size and a data read size in the data storage device do not become so larger than a data write requested size requested from the host device, high random write performance can be obtained. The lifespan of the semiconductor storage element generally depends on an erase count or a write count. In order to increase the design lifespan of the data storage device, the data written size in the data storage device is preferably smaller than the data write requested size requested from the host device.
Meanwhile, in an access pattern with respect to the data storage device, address locality generally exists. In the log-structured method described above, since the address locality of the access pattern is not considered, ordinary use performance cannot be sufficiently improved.